package 动态规划;

public class No279完全平方数 {

    /**
     * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
     * 你需要让组成和的完全平方数的个数最少。
     *
     * 示例 1:
     * 输入: n = 12
     * 输出: 3
     * 解释: 12 = 4 + 4 + 4.
     * 示例 2:
     * 输入: n = 13
     * 输出: 2
     * 解释: 13 = 4 + 9.
     */

    /**
     * 用动态规划求解,找出最小数的完全平方数
     * 假设n=18
     * [+1]->是因为1也是完全平方数
     * f(1)=min(f(0)+1,计算)
     * f(2)=min(f(1)+1,计算)
     * f(3)=min(f(2)+1,计算)
     * f(4)=min(f(3)+1,计算)
     * 计算是不是有讲究?需要计算多个?
     * 所以还要有个for
     * f(4)=min(f(3)+1,f(2)+1);
     */
    public int numSquares(int n) {

        if(n<=1){
            return 1;
        }

        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;

        for (int i = 3; i <= n; i++) {

            //初始让它最坏情况:比上一位多1
            dp[i]=dp[i-1]+1;
            for (int j = 1; j*j <= i; j++) {
                dp[i]=Math.min(dp[i-j*j]+1,dp[i]);
            }

        }

        return dp[n];
    }

    public static void main(String[] args) {
        No279完全平方数 n=new No279完全平方数();
        int result = n.numSquares(12);
        System.out.println(result);
    }

}
